package list;
// 两数相加
public class leetcode2 {
    public static void main(String[] args) {
        int[] nums1 = {9,9,9,9,9,9,9};
        int[] nums2 = {9,9,9,9};
        ListNode l1 = createList(nums1);
        ListNode l2 = createList(nums2);
        ListNode l3 = addTwoNumbers(l1,l2);
        while (l3!=null){
            System.out.print(l3.val + " ");
            l3 = l3.next;
        }
    }

    public static ListNode createList(int[] nums){
        ListNode head = new ListNode(nums[0]);
        ListNode cur = head;
        for (int i = 1; i < nums.length; i++){
            ListNode temp = new ListNode(nums[i]);
            cur.next = temp;
            cur = cur.next;
        }
        return head;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int t = 0;// 记录要不要进位；
        while(l1 != null && l2 != null){
            int value = l1.val + l2.val + t;
            if(value >= 10){
                value = value % 10;
                t = 1;
            }else {
                t = 0;
            }
            ListNode temp = new ListNode(value);
            cur.next = temp;
            l1 = l1.next;
            l2 = l2.next;
            cur = cur.next;
        }

        if(l1 != null){
            while(l1 != null){
                int value = l1.val + t;
                if(value >= 10){
                    value = value % 10;
                    t = 1;
                }
                else {
                    t = 0;
                }
                ListNode temp = new ListNode(value);
                cur.next = temp;
                l1 = l1.next;
                cur = cur.next;
            }
        }
        else if(l2 != null){
            while(l2 != null){
                int value = l2.val + t;
                if(value >= 10){
                    value = value % 10;
                    t = 1;
                }
                else {
                    t = 0;
                }
                ListNode temp = new ListNode(value);
                cur.next = temp;
                l2 = l2.next;
                cur = cur.next;
            }
        }
        if(l1 == null && l2 == null && t == 1){
            cur.next = new ListNode(1);
        }

        return head.next;
    }

    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 虚拟头节点
        ListNode current = dummy;
        int carry = 0; // 进位

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;

            int sum = val1 + val2 + carry;
            carry = sum / 10; // 计算进位
            current.next = new ListNode(sum % 10); // 当前位的值
            current = current.next; // 移动指针

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummy.next; // 返回真正的头节点
    }
}
